Brimstone is the same thing as sulfur. That's what the spell book says.
Sulfur smells like rotten eggs.
Do you know anyone who has a rotten egg?
One of the queens on the Isle of Wonder has one.
She wants the other queen's lump of coal.
You could solve their problems if you found a lump of coal for both queens.